IMPLEMENTATION MODULE Tad_Arbol;

FROM StrIO IMPORT WriteString, WriteLn,WriteString;  
FROM FIO IMPORT OpenToRead,Close,File,Exists,ReadString;
FROM DynamicStrings IMPORT String, ConCat, InitString,CopyOut, char;
FROM Storage IMPORT ALLOCATE, DEALLOCATE;
FROM NumberIO IMPORT ReadInt,WriteInt;
FROM DynamicStrings IMPORT String, Slice, CopyOut, Index, InitString;
FROM StringConvert IMPORT StringToInteger;
FROM Tad_Solicitud IMPORT Solicitud,Imprimir;
FROM FpuIO IMPORT WriteReal;
FROM SYSTEM IMPORT ADDRESS;

TYPE Arbol = POINTER TO RECORD
							raiz : POINTER TO Nodo;
							imprimir : FuncImprimir;
							END;
TYPE Nodo = RECORD
			info : ADDRESS;
			valor : REAL;
			izq,padre,der : Arbol;		
			END;


PROCEDURE Arbol_Crear(funcion : FuncImprimir): Arbol;
VAR arb : Arbol;

   BEGIN
      NEW(arb);
      IF (arb = NIL) THEN
         RETURN arb;
      END;

      arb^.raiz := NIL;
      arb^.imprimir := funcion;

      RETURN arb;
   END Arbol_Crear;

  PROCEDURE Arbol_esVacio(t : Arbol) : BOOLEAN;
  BEGIN
     RETURN t^.raiz = NIL;
  END Arbol_esVacio;

  PROCEDURE Arbol_AsignarRaiz(VAR t : Arbol; e : ADDRESS; n : REAL) : BOOLEAN;
  BEGIN
     IF t = NIL THEN
        RETURN FALSE;
     END;
     t^.raiz^.info := e;
     IF t^.raiz^.info = NIL THEN
        RETURN FALSE;
     END;
     RETURN TRUE;
  END Arbol_AsignarRaiz;


PROCEDURE Agregar_Nodo (VAR arb : Arbol; info : ADDRESS; valor : REAL) : BOOLEAN;
VAR nuevo,aux1,aux2 : Arbol;
VAR valido : BOOLEAN;
BEGIN
	NEW(nuevo);
	
	IF nuevo = NIL THEN
		RETURN FALSE;
	END;
	
	nuevo^.raiz^.valor := valor;
	nuevo^.raiz^.info := info;
	
	aux1 := arb;
	aux2 := NIL; (*papa de aux1*)
	
	IF (arb^.raiz^.izq = NIL) AND (arb^.raiz^.der = NIL) AND (arb^.raiz^.valor = 0.0) THEN
		valido := Arbol_AsignarRaiz(arb,info,valor);
		IF NOT valido THEN
			RETURN FALSE;
		END;
		RETURN TRUE;
	END;
	
	WHILE aux1 <> NIL DO
		aux2 := aux1;
		
		IF valor < aux1^.raiz^.valor THEN
			aux1 := aux1^.raiz^.izq;
		ELSE
			aux1 := aux1^.raiz^.der;
		END;
	END;
	
	nuevo^.raiz^.padre := aux2;
	
	IF aux2^.raiz^.valor <= valor THEN
		aux2^.raiz^.der := nuevo;
	ELSE
		aux2^.raiz^.izq := nuevo;
	END;
	
	RETURN TRUE;

END Agregar_Nodo;

PROCEDURE AgregarNodo (VAR arb : Arbol; info : ADDRESS; valor : INTEGER) : BOOLEAN;
VAR x : REAL;
BEGIN
	x:= FLOAT(valor);
	RETURN Agregar_Nodo(arb,info,x);
END AgregarNodo;

PROCEDURE Buscar (arb : Arbol; clave : REAL) : ADDRESS;
VAR nod : Arbol;
BEGIN
	IF arb = NIL THEN
		RETURN NIL;
	END;
	
	nod := arb;
	
	WHILE (nod <> NIL) AND (nod^.raiz^.valor <> clave) DO
		IF (nod^.raiz^.valor >= clave) THEN
			nod := nod^.raiz^.izq;
		ELSE 
			nod := nod^.raiz^.der;
		END;
	END;
	
	IF nod = NIL THEN
		WriteLn();
		WriteString('El elemento no se encuentra en el arbol');
		RETURN NIL;
	END;
	RETURN nod^.raiz^.info;
	
END Buscar;

PROCEDURE Arbol_ImprimirValores(arb : Arbol);
  BEGIN
    IF arb = NIL THEN
      RETURN;
    ELSE
      IF arb^.raiz^.der = NIL THEN
        Arbol_ImprimirValores(arb^.raiz^.der);
      END;
	arb^.imprimir(arb^.raiz);
      IF arb^.raiz^.izq = NIL THEN
        Arbol_ImprimirValores(arb^.raiz^.izq);
      END;
    END;
  END Arbol_ImprimirValores;
  
PROCEDURE Arbol_Lista(arb : Arbol; VAR lista : Lista);
VAR valido : BOOLEAN;
BEGIN
    IF arb = NIL THEN
      RETURN;
    ELSE
      IF arb^.raiz^.der = NIL THEN
        Arbol_Lista(arb^.raiz^.der,lista);
      END;
	valido := Lista_Agregar(lista,arb^.raiz);
	IF NOT valido THEN
		WriteLn();
		WriteString('El elemento a sido agregado de forma incorrecta');
		WriteLn();
	END;
      IF arb^.raiz^.izq = NIL THEN
        Arbol_Lista(arb^.raiz^.izq,lista);
      END;
    END;
  END Arbol_Lista;

PROCEDURE Arbol_ListaOrdenada(arb : Arbol) : Lista;
VAR lista : Lista;
BEGIN
	lista := Crear_Lista(arb^.imprimir);
	Arbol_Lista(arb,lista);
	RETURN lista;
END Arbol_ListaOrdenada;

END Tad_Arbol.
